package backtrack;

/**
 * create by yongli on 2021-07-13 08:46
 */

class Solution79 {

    public static void main(String[] args) {
        Solution79 sol = new Solution79();
        char[][] board = {{'a', 'b'}, {'c', 'd'}};
        String word = "dbac";
        sol.exist(board, word);

    }

    private boolean flag = false;

    public boolean exist(char[][] board, String word) {

        int m = board.length, n = board[0].length;
        String str = "";
        // 默认flase
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    // System.out.println(i);
                    // System.out.println(j);
                    boolean[][] map = new boolean[m][n];
                    map[i][j] = true;
                    walk(board, i, j, map, word.substring(0, 1), word);
                }
            }
        }

        return flag;
    }

    /**
     * 和八皇后问题，没有什么区别，就是回溯，在回溯的过程中枝减
     * （i,j)--> (i+1,j),(i,j+1),(i-1,j),(i,j-1); 以前没有走过的路
     * 没有正确表示转态
     */
    public void walk(char[][] board, int i, int j, boolean[][] map, String str, String word) {
        if (flag) {
            return;
        }
        // 可能的情况，枝减
        if (str.length() > word.length()) {
            return;
        }
        // System.out.println(str);

        if (str.equals(word)) {
            flag = true;
            return;
        }

        // 四个方向
        System.out.println(i);
        System.out.println(j);
        if (j - 1 >= 0 && !map[i][j - 1]) {

            String str2 = str + board[i][j - 1];
            if (word.startsWith(str2)) {
                boolean[][] map2 = copy(map);
                // 变量隔离
                map2[i][j - 1] = true;
                walk(board, i, j - 1, map2, str2, word);
            }
        }

        if (i + 1 < board.length && !map[i + 1][j]) {

            String str2 = str + board[i + 1][j];
            System.out.println(board[i + 1][j]);
            if (word.startsWith(str2)) {
                boolean[][] map2 = copy(map);
                map2[i + 1][j] = true;
                walk(board, i + 1, j, map2, str2, word);
            }
        }

        if (j + 1 < board[0].length && !map[i][j + 1]) {

            String str2 = str + board[i][j + 1];
            if (word.startsWith(str2)) {
                boolean[][] map2 = copy(map);
                map2[i][j + 1] = true;
                walk(board, i, j + 1, map2, str2, word);
            }
        }

        if (i - 1 >= 0 && !map[i - 1][j]) {

            String str2 = str + board[i - 1][j];
            if (word.startsWith(str2)) {
                boolean[][] map2 = copy(map);
                map2[i - 1][j] = true;
                walk(board, i - 1, j, map2, str2, word);
            }
        }

    }

    public boolean[][] copy(boolean[][] map) {
        int m = map.length, n = map[0].length;
        boolean[][] map2 = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                map2[i][j] = map[i][j];
            }
        }
        return map2;
    }
}
